#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<mpi.h>
#include<time.h>
#include<iostream>
#include<list>

using namespace std;

#define TAM_MAX_PALAVRA 100
#define TAM_MAX_PRIMO 2000
#define BILLION 1E9

/* Retorna a soma do calor ASCII de cada letra de uma palavra */
int soma_letras(char string[]){
	int i, tam, soma = 0;

	tam = strlen(string);

	for(i = 0; i < tam; i++)
		soma = soma + string[i];

	return soma;
}

/* Retorna 1 se o numero n for primo, se não retorna 0 */
int primo(int n){
	int i, j, raiz;
	int vetorPrimos[TAM_MAX_PRIMO];

	raiz = sqrt(n);

	for(i = 2; i <= n; i++)
		vetorPrimos[i] = i;

	for(i = 2; i <= raiz; i++)
		if (vetorPrimos[i] == i) 
			for(j = i*i; j <= n; j=j+i)
				vetorPrimos[j] = 0;

	return ((vetorPrimos[n] == 0) ? 0 : 1);
}

/* Retorna 1 se a string é um palindromo, se não retorna 0 */
int palindromo(char string[]){
	int i, tam, tam_aux, flag = 1;
	char string_aux[TAM_MAX_PALAVRA];

	strcpy(string_aux, string);

	tam = strlen(string_aux);
	tam_aux = tam/2;

	for(i = 0; i < tam; i++)
		if(isupper(string_aux[i]))
			string_aux[i] = tolower(string_aux[i]);

	for(i = 0; i < tam_aux; i++){
		if(string_aux[i] != string_aux[tam-i-1])
			flag = 0;
	}

	return flag;
}

/* Faz o pre-processamento do arquivo wikipedia.txt e separa ele em (noProcesses-1) arquivos */
void separaArquivo(int noProcesses){
	int num_palavras = 0, i;
	char aux_arq[5], c, c_ant;
	FILE *fp, *fp_out[noProcesses-1];

	strcpy(aux_arq, "k.txt");

	/* Abrimosos arquivos 0.txt, 1.txt, ..., (noProcesses-2).txt */
	for(i = 0; i < noProcesses-1; i++){
	        aux_arq[0] = (char)(((int)'0')+i);
	        fp_out[i] = fopen(aux_arq, "w+");
	}

	/* Vamos realizar o pré-processamento do texto e separa-lo */
	fp = fopen("wikipedia.txt", "r+");
	i = 0;
	c = fgetc(fp);
	c_ant = 'a';
	while(c != EOF){
	        /* Se for diferente de numeros ou letras, colocamos _ */
	        if(!(c >= '0' && c <= '9') && !(c >= 'a' && c <= 'z') && !(c >= 'A' && c <= 'Z'))
	                fputc('_', fp_out[i]);
	        else
	                fputc(c, fp_out[i]);

	        /* Se é espaço ou fim de linha, e o caracter anterior não é ' ' quer dizer que chegamos no final de uma palavra */
	        if((c == ' ' || c == '\n') && c_ant != ' ')
	                num_palavras++;

	        /* Se o número de palavras for igual ao 8917904/noProcesses-1, mudamos o arquivo */
	        if(num_palavras == (8917904/(noProcesses-1)) && i != (noProcesses-2)){
	                i++;
	                num_palavras = 0;
	        }
		c_ant = c;
        	c = fgetc(fp);
	}

	/* Fecha os ponteiros de arquivo abertos */
	fclose(fp);
	for(i = 0; i < noProcesses-1; i++)
		fclose(fp_out[i]);
}

/* Esta função recebe um array de listas e um rank, para o rank 1 a função pega o arquivo 0.txt 
 * e coloca as palavras dele na lista palavras[0] */
void separaListas(list<string> *palavras, int rank){
	char c, aux_arq[5], palavra[TAM_MAX_PALAVRA];
	int flag, i;
	FILE *fp_final;

	list<string>::iterator it = palavras[rank-1].begin();

	strcpy(aux_arq, "k.txt");

	/* Abrimos o arquivo, se estamos no rank 1, abrimos o arquivo 0.txt */
	aux_arq[0] = (char)(((int)'0')+(rank-1));
	fp_final = fopen(aux_arq, "r+");

	/* Agora voltamos para o inicio do arquivo e separamos as palavras */
	c = fgetc(fp_final);
	i = 0;
	while(c != EOF){
		if(c != '_') /* nosso delimitador é _ */
			palavra[i++] = c;
		else if (i != 0)
			flag = 1;

		if(flag == 1){
			palavra[i] = '\0';
			if(i > 1)
				palavras[rank-1].insert(it, palavra);
			i = 0;
			flag = 0;
		}
		c = fgetc(fp_final);
	}

	fclose(fp_final);
}

/* Percorre a lista e vê se a palavra é palindromo, se for vê se o mapeamento ASCII é primo */
void numeroPalindromosPrimos(list<string> *palavras, int rank, int *num_palindromos, int *num_primos){
	int i;
	char palavra[TAM_MAX_PALAVRA];
	list<string>::iterator it;
	string aux;

	/* Percorre a lista procurando palindromos, excluimos as palavras que não são aplindromos da lista */
	for(it = palavras[rank-1].begin(); it != palavras[rank-1].end(); it++){
		aux = *it;

		/* Passamos a palavra de string (c++) para um array de chars (c) */
		for(i = 0; i < aux.size(); i++)
			palavra[i] = aux[i];
		palavra[i] = '\0';

		if(palindromo(palavra)){
			(*num_palindromos)++;
			if(primo(soma_letras(palavra)))
				(*num_primos)++;
		}
	}
}

int main(int argc, char **argv){
	int k, total_palindromos = 0, total_primos = 0;
	int a, b, c, sinal;
	int rank, noProcesses;
	struct timespec time1, time2;
	double diff;
	int valor[2] = {0,0};

	/* Inicializamos MPI */
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &noProcesses);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	MPI_Status Stat;

	list<string> palavras[noProcesses-1];
	list<string>::iterator it;
	string aux;

	/* Se estamos no processo 0, o "mestre", vamos separar o arquivo wikipedia em vários outros arquivos 
	 * Nos outros processos vamos colocar as palavras em listas diferentes */
	if(rank == 0){
		separaArquivo(noProcesses);

		/* Da um boradcast para que os outros processos possam continuar */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);
	} else {
		/* Esperam o processo mestre */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);

		separaListas(palavras, rank);

		/* Envia sinal para o mestre que está esperando a separação das listas */
		MPI_Send(&sinal, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
	}


	/************************ Procura os Palindromos ************************/

	/* O processo 0 espera todos estarem prontos para começar a contar o tempo */
	if(rank == 0){
		/* O mestre espera a separação de todas as listas */
		for(k = 1; k < noProcesses; k++)
			MPI_Recv(&sinal, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);

		clock_gettime(CLOCK_REALTIME, &time1);

		/* Da um boradcast para que os outros processos possam continuar */
		MPI_Bcast(&b, 1, MPI_INT, 0, MPI_COMM_WORLD);
	} else {
		/* Esperam o processo mestre */
		MPI_Bcast(&b, 1, MPI_INT, 0, MPI_COMM_WORLD);

		for(k = 1; k < noProcesses; k++)
			if(k == rank){
				numeroPalindromosPrimos(palavras, rank, &valor[0], &valor[1]);

				/* Envia sinal para o mestre que está esperando o termino da verificação de palindromos */
				MPI_Send(&valor, 2, MPI_INT, 0, rank, MPI_COMM_WORLD);
			}
	}

	/* O processo 0 espera todos terminarem para terminar de contar o tempo */
	if(rank == 0){
		/* O mestre espera a verificação de palindromos */
		for(k = 1; k < noProcesses; k++){
			MPI_Recv(&valor, 2, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
			total_palindromos += valor[0];
			total_primos += valor[1];
		}

		clock_gettime(CLOCK_REALTIME, &time2);

		diff = (time2.tv_sec-time1.tv_sec)+(time2.tv_nsec-time1.tv_nsec)/BILLION;

		printf("Numero de palindromos no texto: %d\n", total_palindromos);
		printf("Numero de primos nos palindromos: %d\n", total_primos);
		printf("Tempo para verificação de palindromos: %lf segundos\n", diff);
	}

	MPI_Finalize();

	return 0;
}
